1. Technical Field
This invention relates to processors and methods for solving assignment problems and, in particular, to processors and methods for solving large constrained assignment problems in real time.
2. Discussion
The solution of large scale assignment problems is a major challenge to conventional data processing 10 systems. Generally, in assignment problems a number of elements are to be selected from among many others and assigned to other elements in such a way as to force to the entire assignment over all the elements to be optimal in some sense. Part of the difficulty of association problems is that they are generally not solvable with a single solution but, instead, there may be a range of solutions over which the best solution is sought. Moreover, association problems frequently involve a combinatorial "explosion" or exponential blow up, in the number of possible answers. Association problems are found in a number of applications, including among others, resource allocation, object association, data fusion, pattern matching, and manufacturing inspection systems.
Most of the current approaches to solving these problems have a number of drawbacks. These often involve difficulties in developing algorithms and software. Also, an inordinate amount of CPU time is usually required once the algorithms and software have been developed. One example is in the area of resource allocation. This field involves the efficient optimization of the allocation of technological or industrial resources. One commonly used technique for resource allocation is called linear programming. A linear programming model consists of a number of linear expressions that represent the quantitative relationships between the various possible allocations, their constraints, and their costs or their benefits. The set of relationships is said to be linear if all of the relationships are sums of constant coefficients multiplied by unknown allocation values which are equal to, greater than or equal to, or less than or equal to, a constant. Unfortunately, many resource allocation problems cannot be represented by such linear relationships but involve higher powers of unknowns or non-linearities in the relationships and thus are not solvable using linear programming approaches.
For allocations problems which do fit the linear programming model, the most commonly used approach is called the Simplex method, developed by G. B. Dantzig in 1946. More recently, the barrier, interior point (Karmarkar) method improved upon the simplex method. See U.S. Pat. No. 4,744,028 issued to Karmarkar. However, even improved linear programming techniques still require an inordinate amount of processing time for large scale problems thus precluding their use in real time applications. In this context, real time is defined as providing an optimum allocation sufficiently fast to provide more or less continuous control of an ongoing process, system for apparatus. Further, linear programming techniques still require extensive front end analysis which must be redone for each new nuance in the assignment problem structure. Also, these approaches exhibit a high sensitivity to input data scaling.
In view of the forgoing, it would be desirable to have a system which can solve large constrained assignment problems in real time. Further, it would be desirable to have such a system which can achieve well-balanced near optimal assignments at high speeds. Also, it would be desirable to have an assignment processor which requires minimal algorithm development, minimal software development, and minimal preprocessing.
In addition, it would be desirable to have such a system which is tolerant of coarsely normalized input data and which is also able to adapt quickly to small changes in the assignment problem structure. Finally, it would be desirable to have an assignment processor which can be constructed at low cost utilizing low complexity hardware components.